public class ArraySort_hjl {

    public static void main(String[] args) {
        int[] array = {-4, 2, 10, 9, 8, 7, 6};
        int k = 0;
        searchSortNumber(array, k, false);
    }

    /**
     * 给定一组数组， 给一数组a[1…n]，选出其中第K小(大)的那个数
     *
     * @param array
     * @param k
     * @param reverse false：找第K小的
     *                true: 找第K大的
     */
    private static void searchSortNumber(int[] array, int k, boolean reverse) {
        if (array == null || array.length < 1) {
            System.out.print("数组为空！");
            return;
        }
        if (k < 1) {
            System.out.print("k值需大于0！");
            return;
        }
        if (array.length < k) {
            System.out.print("输入的K值不能超出数组大小！");
            return;
        }
        arraySort(array, 0, array.length);
        System.out.print("排序后的数组为: ");
        printArray(array);
        int position = reverse ? array.length - k : k - 1;
        System.out.println("找到数组中第" + k + (reverse ? "大" : "小") + "元素为: " + array[position]);
    }

    private static void arraySort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        /*找出基数，将数组分为两份*/
        int temp = findBaseData(array, left, right);
        arraySort(array, left, temp);
        arraySort(array, temp + 1, right);
    }

    /**
     * 找出基准位置
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int findBaseData(int[] array, int left, int right) {
        int temp = array[left];
        while (left < right) {
            while (left < right) {
                if (temp > array[--right]) {
                    swap(array, left, right);
                    break;
                }
            }
            while (left < right) {
                if (temp < array[++left]) {
                    swap(array, left, right);
                    break;
                }
            }
        }
        return left;
    }

    /**
     * 交换数组中的两个数
     *
     * @param array
     * @param left
     * @param right
     */
    private static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    private static void printArray(int[] array) {
        int arraySize = array.length;
        for (int index = 0; index < arraySize; index++) {
            System.out.print(array[index] + " ");
        }
        System.out.println();
    }

}
